#ifndef ALGO_H_
#define ALGO_H_

#include <algorithm>
#include <cstddef>
#include <cstdlib>
#include <vector>

namespace lxj
{
// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
inline std::vector<int> sortArrayByParityII(std::vector<int>& nums)
{
    auto swap = [&nums](int i, int j) {
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    };

    for (int even = 0, odd = 1, end = nums.size() - 1; even < nums.size() && odd < nums.size();) {
        if (nums[end] % 2 == 0) {
            swap(end, even);
            even += 2;
        }
        if (nums[end] % 2 != 0) {
            swap(end, odd);
            odd += 2;
        }
    }
    return nums;
}

// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
inline int findDuplicate(std::vector<int>& nums)
{
    int fast = nums[0], slow = nums[0];
    do {
        fast = nums[nums[fast]];
        slow = nums[slow];
    } while (fast != slow);
    fast = nums[0];
    while (fast != slow) {
        fast = nums[fast];
        slow = nums[slow];
    }
    return slow;
}

// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
// 解法1
// 辅助数组的解法（不是最优解）
// 时间复杂度O(n)，额外空间复杂度O(n)
inline int trap1(std::vector<int>& height)
{
    int              n = height.size();
    std::vector<int> left(n), right(n);
    left[0]      = height[0];
    right[n - 1] = height[n - 1];
    for (int i = 1; i < n; i++) {
        left[i] = std::max(height[i], left[i - 1]);
    }
    for (int i = n - 2; i >= 0; i--) {
        right[i] = std::max(height[i], right[i + 1]);
    }

    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        ans += std::max(0, std::min(left[i], right[i]) - height[i]);
    }
    return ans;
}
// 双指针的解法（最优解）
// 时间复杂度O(n)，额外空间复杂度O(1)
inline int trap2(std::vector<int>& height)
{
    int l = 1, r = height.size() - 2, lmax = height[0], rmax = height[height.size() - 1];
    int ans = 0;
    while (l <= r) {
        if (lmax <= rmax) {
            ans += std::max(0, lmax - height[l]);
            lmax = std::max(lmax, height[l++]);
        }
        else {
            ans += std::max(0, rmax - height[r]);
            rmax = std::max(rmax, height[r--]);
        }
    }
    return ans;
}

// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
inline int numRescueBoats(std::vector<int>& people, int limit)
{
    std::sort(people.begin(), people.end());
    int l = 0, r = people.size() - 1;
    int ans = 0, sum = 0;
    while (l <= r) {
        sum = l == r ? people[r] : people[l] + people[r];
        if (sum > limit) {
            r--;
        }
        else {
            l++;
            r--;
        }
        ans++;
    }
    return ans;
}

// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
// 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
inline int maxArea(std::vector<int>& height)
{
    int ans = 0;
    for (int l = 0, r = height.size() - 1, product; l <= r;) {
        product = std::min(height[l], height[r]) * (r - l);
        ans     = ans > product ? ans : product;
        if (height[l] < height[r])
            l++;
        else
            r--;
    }
    return ans;
}

// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
inline int findRadius(std::vector<int>& houses, std::vector<int>& heaters)
{
    auto best = [&](int i, int j) {
        return j == heaters.size() - 1 ||
               std::abs(heaters[j] - houses[i]) < std::abs(heaters[j + 1] - houses[i]);
    };
    std::sort(houses.begin(), houses.end());
    std::sort(heaters.begin(), heaters.end());

    int ans = 0;
    for (int i = 0, j = 0; i < houses.size(); i++) {
        while (!best(i, j)) j++;
        ans = std::max(ans, std::abs(houses[i] - heaters[j]));
    }
    return ans;
}

// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
inline int firstMissingPositive(std::vector<int>& nums)
{
    auto swap = [&](int l, int r) {
        int temp = nums[l];
        nums[l]  = nums[r];
        nums[r]  = temp;
    };
    int l = 0, r = nums.size();
    while (l < r) {
        if (nums[l] == l + 1) {
            l++;
        }
        else if (nums[l] > r || nums[l] <= l || nums[nums[l] - 1] == nums[l]) {
            swap(l, --r);
        }
        else {
            swap(l, nums[l] - 1);
        }
    }
    return l + 1;
}
}   // namespace lxj

#endif